// 模拟
// 思路比较简单 - 直接根据题目要求进行模拟
// 一定要在演草纸上手动模拟算法流程，避免凭空想象
// 难度高的模拟题，往往都需要找规律，才能简化，否则代码不好写，并且时间/空间复杂度较高

// 例题 5：
// 给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。
// 由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。
//
//        请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
//
//        要想发出蛙鸣 "croak"，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。
//        如果没有输出全部五个字母，那么它就不会发出声音。
//        如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。
//
//        示例 1：
//
//        输入：croakOfFrogs = "croakcroak"
//        输出：1
//        解释：一只青蛙 “呱呱” 两次
//        示例 2：
//
//        输入：croakOfFrogs = "crcoakroak"
//        输出：2
//        解释：最少需要两只青蛙，“呱呱” 声用黑体标注
//        第一只青蛙 "crcoakroak"
//        第二只青蛙 "crcoakroak"
//        示例 3：
//
//        输入：croakOfFrogs = "croakcrook"
//        输出：-1
//        解释：给出的字符串不是 "croak" 的有效组合。
//
//
//        提示：
//
//        1 <= croakOfFrogs.length <= 105
//        字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'

// 解题思路：
// 模拟题目中的过程，青蛙叫出一种声音后，一定要让前面的声音数量 - 1，这种声音 + 1
// 青蛙叫第一种声音的时候，要判断有没有叫完的青蛙，有叫完的就接着叫
// 没有叫完的，就再用另外一个青蛙叫

import java.util.HashMap;
import java.util.Map;

public class MinNumberOfFrogs {
    public int minNumberOfFrogs(String croakOfFrogs) {
        String t = "croak";
        int n = t.length();
        // 统计每种叫声的数量
        int[] hash = new int[n];
        // 建立每种叫声和叫声数量下标的映射关系
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            char ch = t.charAt(i);
            map.put(ch, i);
        }
        char[] c = croakOfFrogs.toCharArray();
        for(int i = 0; i < c.length; i++){
            // 处理第一种叫声
            if(c[i] == t.charAt(0)){
                if(hash[n - 1] >0) hash[n - 1]--;
                hash[0]++;
            }else{
                // 处理后面的多种叫声
                int index = map.get(c[i]);
                if(hash[index - 1] == 0) return -1;
                else{
                    hash[index - 1]--;
                    hash[index]++;
                }
            }
        }
        for(int i = 0; i < n - 1; i++){
            if(hash[i] > 0) return -1;
        }
        return hash[n - 1];
    }
}
